/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv
@Language: C++
@Datetime: 16-02-09 08:52
*/

class Solution {
public:
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(int k, vector<int> &prices) {
        // write your code here
        if (prices.size()<2 || k<1)
            return 0;
        
        if (k>=prices.size()/2){
            int profit=0;
            for(int i=1;i<prices.size();++i)
                if (prices[i]>prices[i-1])
                    profit += prices[i]-prices[i-1];
            return profit;
        }
        
        vector<vector<int> > global,local;
        vector<int> kblock;
        for(int i=0;i<=k;++i)
            kblock.push_back(0);
        for(int i=prices.size();i;--i){
            global.push_back(kblock);
            local.push_back(kblock);
        }
        
        int diff=0;
        for(int i=1;i<prices.size();++i){
            diff = prices[i]-prices[i-1];
            for(int j=1;j<=k;++j){
                if (global[i-1][j-1]+(diff>0?diff:0) > local[i-1][j]+diff)                local[i][j] = global[i-1][j-1]+(diff>0?diff:0);
                else
                    local[i][j] = local[i-1][j]+diff;
                global[i][j] = (global[i-1][j]>local[i][j]
                    ?global[i-1][j]:local[i][j]);
            }
        }
        return global[prices.size()-1][k];
    }
};